package com.zjw.algorithm.ready1;


import com.zjw.algorithm.utils.ListNode;

/**
 * Definition for singly-linked list.
 * class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class _环形链表2 {

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode fastP = head;
        ListNode slowP = head;

        while (fastP != null) {
            fastP = fastP.next;

            slowP = slowP.next;


            //快指针移动两个单位
            if (fastP == null) {
                return null;
            } else {
                fastP = fastP.next;
            }

            if (fastP == slowP) {
                //find cross
                break;
            }
        }
        if (fastP == null){
            return null;
        }

        slowP = head;

        while (slowP != fastP) {
            slowP = slowP.next;
            fastP = fastP.next;
        }

        return slowP;
    }
}
